import * as L from 'leaflet'

/**
 * The Z-index offset to apply to inflated markers to make them show on top
 * of deflated markers
 */
const INFLATED_MARKERS_ZINDEX_OFFSET = 10000

/**
 * The Z-index offset to apply to deflated markers to make them show on top
 * of all markers when the special 'show hidden markers' action is used
 */
const DEFLATED_MARKERS_ZINDEX_OFFSET = 20000

/**
 * A two-state marker that can be added to a InflatableMarkerGroup
 *
 * An inflatable marker can be either inflated (it's displayed normally)
 * or deflated (it's displayed as a smaller different icon to declutter the
 * map).
 *
 * This class is not normally used by end-users. Normal markers should be
 * added to L.InflatableMarkerGroup instead and the group will manage its
 * own L.InflatableMarker-s.
 *
 * To handle the two inflated/deflated states and the associated changes in
 * shape and size, instances of this class are also their own icons.
 * Toggling between the inflated and deflated state boils down to toggle the
 * display of the base marker's icon (shown when inflated) and this class'
 * icon (shown when deflated).
 * @extends L.Marker
 */
const InflatableMarker = L.Marker.extend({
    /**
     * The options applicable to the marker, same as the Icon options but
     * an explicit size in mandatory
     * @public
     * @type {L.IconOptions}
     */
    options: L.Icon.prototype.options,

    /**
     * Constructs the marker.
     * @constructs L.InflatableMarker
     * @public
     * @param {L.LatLng} latlng - The position of the marker on the map
     * @param {L.InflatableMarkerGroup} group - The group this marker belongs to,
     * marker collisions are only computed inside a single group
     * @param {L.Layer} baseMarker - The inflated version of the marker, added to the
     * group via addLayer(...)
     */
    initialize: function (latlng, group, baseMarker) {
        L.Util.setOptions(this, baseMarker.options)
        this.options.pane = group.options.pane
        // hijack the icon drawing process
        this.options._inflatedIcon = this.options.icon
        this.options.icon = this

        /**
         * The underlying marker added to the group, used as the inflated
         * version of the current inflatable marker
         * @public
         * @type {L.Marker}
         */
        this.baseMarker = baseMarker

        /**
         * Where the marker is displayed
         * @private
         * @type {L.LatLng}
         */
        this._latlng = latlng

        /**
         * The clearance box around the marker in the order (north, east, south, west)
         * @type {[number, number, number, number]}
         * @private
         */
        this._borders = [null, null, null, null]

        /**
         * The L.InflatableMarkerGroup this marker belongs to
         * @private
         * @type {L.InflatableMarkersGroup}
         */
        this._group = group

        /**
         * The set of all markers which collision with the current marker if
         * they're both inflated
         * @private
         * @type {Set<L.InflatableMarker>}
         */
        this._obstructiveMarkers = new Set()

        /**
         * Whether the marker is currently inflated
         * @private
         * @type {boolean}
         */
        this._inflated = false

        /**
         * Whether the marker's icon needs to be redrawn, typically after a
         * change from inflated to deflated or vice-versa
         * @private
         * @type {boolean}
         */
        this._iconNeedsUpdate = true

        /**
         * The original Z-index attributed to this marker
         * @private
         * @type {integer}
         */
        this._savedZIndexOffset = this.options.zIndexOffset

        this.addEventParent(this.baseMarker)

        this.on('contextmenu', this.toggle, this)
    },

    _computeBorders: function (map, margin) {
        const pos = map.latLngToContainerPoint(this._latlng)
        const halfSize = L.point(this.options._inflatedIcon.options.iconSize).divideBy(2)
        const br = pos.add(halfSize).add(margin)
        const ul = pos.subtract(halfSize).subtract(margin)
        this._borders = [ul.y, br.x, br.y, ul.x]
    },

    /**
     * Gets the size of the marker when inflated.
     * @public
     * @return {L.Point} The inflated size of the marker
     */
    getInflatedSize: function () {
        const iconOptions = this.options._inflatedIcon.options
        if (!(iconOptions.iconSize instanceof L.Point))
            iconOptions.iconSize = L.point(iconOptions.iconSize)
        return iconOptions.iconSize
    },

    /**
     * Returns the icon to be displayed on the map, depending on its
     * inflated/deflated state.
     * @public
     * @return {HTMLElement} The icon to draw
     */
    createIcon: function () {
        this._iconObj = this._inflated
            ? this.options._inflatedIcon
            : this._group.options.iconCreateFunction(this)
        return this._iconObj.createIcon()
    },

    /**
     * Returns the shadow to be displayed on the map, alongside with the
     * icon.
     * @public
     * @todo This is not implemented for now and returns null (no shadow)
     * @return {HTMLElement} The shadow to add to the icon
     */
    createShadow: function () {
        return null
    },

    /**
     * Forces the icon to be redrawn, for example if its inflated/deflated
     * state has been modified externally.
     * @public
     */
    redraw: function () {
        if (this._inflated) {
            this.setIcon(this.options._inflatedIcon)
        } else {
            this.setIcon(this._group.options.iconCreateFunction(this))
        }
    },

    /**
     * Sets another marker as conflicting/collisioning with the current one.
     * @private
     * @param {L.InflatableMarker} otherMarker - Another marker in the group
     */
    _addObstructiveMarker: function (otherMarker) {
        this._obstructiveMarkers.add(otherMarker)
        otherMarker._obstructiveMarkers.add(this)
    },

    /**
     * Sets another marker as NOT conflicting/collisioning with the current
     * one (for example, if it's getting removed altogether or reduced in
     * size).
     * @private
     * @param {L.InflatableMarker} otherMarker - Another marker in the group
     */
    _removeObstructiveMarker: function (otherMarker) {
        this._obstructiveMarkers.delete(otherMarker)
        otherMarker._obstructiveMarkers.delete(this)
    },

    /**
     * Removes all markers from the conflicting/collisioning set of the
     * current one.
     * @private
     */
    _clearObstructiveMarkers: function () {
        for (const other of this._obstructiveMarkers) {
            this._removeObstructiveMarker(other)
        }
    },

    /**
     * Returns the set of all markers conflicting/collisioning to the
     * current one.
     * @private
     * @return {Set<L.InflatableMarker>} The conflicting/collisioning
     * markers.
     */
    _getObstructiveMarkers: function () {
        return this._obstructiveMarkers
    },

    /**
     * Puts a marker on top, this is used to ensure for instance that
     * inflated markers are shown on top by default
     * @private
     * @param {int} offset - The offset by which to increase the Z-index of
     * the marker
     */
    _bringToFront: function (offset = INFLATED_MARKERS_ZINDEX_OFFSET) {
        this.setZIndexOffset(offset)
    },

    /**
     * Puts a marker back where it was after it has been brought onto top.
     * @private
     */
    _bringBackFromFront: function () {
        this.setZIndexOffset(this._savedZIndexOffset)
    },

    /**
     * Switches the marker to the inflated state (or no-op if it was already
     * inflated).
     * @private
     */
    _inflate: function () {
        if (this._inflated) return
        this._bringToFront()
        this._inflated = true
        this._iconNeedsUpdate = true
    },

    /**
     * Switches the marker to the deflated state (or no-op if it was already
     * inflated).
     * @private
     */
    _deflate: function () {
        if (!this._inflated) return
        if (this._group._inflatedMarkersAbove) this._bringBackFromFront()
        else this._bringToFront(DEFLATED_MARKERS_ZINDEX_OFFSET)
        this._inflated = false
        this._iconNeedsUpdate = true
    },

    /**
     * Toggles the inflated/deflated state of the marker
     * @public
     */
    toggle: function () {
        if (this._inflated) {
            this._deflate()
        } else {
            this._inflate()
            for (const other of this._obstructiveMarkers) {
                other._deflate()
            }
        }

        // call daddy to refresh everybody
        this._group._refreshIcons()
    },

    /**
     * Tells whether the marker is currently inflated
     * @public
     * @return {boolean} Whether the marker is inflated
     */
    isInflated: function () {
        return this._inflated
    },
})

/**
 * A group of inflatable markers that can be added onto a leaflet map.
 *
 * This class should be used as a regular L.FeatureGroup but for now, users
 * should stick to L.Marker objects. Other features are not explicitly
 * supported (but have never been tested so who knows?). In any case, this
 * class handled its own L.InflatableMarker, so end-users should not
 * construct them manually but instead add the normal markers to this group.
 *
 * The markers group make sure that two conflicting markers (i.e. markers
 * that would collision if they are both inflated) are never inflated at the
 * same time. This makes the map much more readable while keeping the
 * markers at their place on the map, as long as the deflated icon of each
 * marker is carefully chosen not to clutter the map.
 * @extends L.FeatureGroup
 */
const InflatableMarkersGroup = L.FeatureGroup.extend({
    /**
     * How to configure the markers group, additionally from the
     * L.FeatureGroup options
     * @public
     */
    options: {
        /**
         * The margin that must be kept clear around an inflated marker.
         *
         * Any marker closer to the current marker than this clearance will
         * be marked as collisioning. The first element is the horizontal
         * margin, the second one the vertical margin. It's set by default
         * to [2, 2] (pixels). You can set it to [0, 0] or even to a
         * negative value to tolerate some amount of overlapping between
         * inflated markers.
         */
        obstructionSize: L.point(2, 2),
        /**
         * The function that will be used to create deflated markers' icons.
         */
        iconCreateFunction: null,
        /**
         * The map pane this group has to be added to, by default the
         * markers pane
         */
        groupPane: L.Marker.prototype.options.pane,
    },

    /**
     * Constructs an InflatableMarkersGroup
     * @constructs {L.InflatableMarkersGroup}
     * @param {L.InflatableMarkersGroup.options} options - The configuration options
     */
    initialize: function (options) {
        L.Util.setOptions(this, options)
        if (!this.options.obstructionSize instanceof L.Point)
            this.options.obstructionSize = L.point(this.options.obstructionSize)

        /**
         * The underlying layer group used to handle the map layer adding and
         * removal operations
         * @private
         * @type {L.FeatureGroup}
         */
        this._featureGroup = L.featureGroup()

        /**
         * A associative array between base Leaflet layers (the one added to
         * this group) and the corresponding inflatable markers this group
         * constructs.
         *
         * Note: this attribute is a Map but a Javascript one (i.e. an
         * associative array), not a Leaflet Map!
         * @private
         * @type {Map<L.Layer, L.InflatableMarker>}
         */
        this._markers = new Map()

        /**
         * The boundaries of this layer group
         * @private
         * @type {L.LatLngBounds}
         */
        this._bounds = null

        /**
         * Whether this group has already been initialized and added to a map,
         * setting it to false will force recompute all the InflatableMarker-s
         * collisions.
         * @private
         * @type {boolean}
         */
        this._alreadyDisplayed = false

        /**
         * Whether the inflated markers should be displayed on top of deflated
         * markers (the default) or the opposite (to make masked deflated
         * markers prominent).
         * @type {boolean}
         */
        this._inflatedMarkersAbove = true

        /**
         * Other InflatableMarkersGroup that could be added to the same map and
         * whose member markers may collision with the current group.
         * @type {Set<L.InflatableMarkersGroup>}
         */
        this._otherGroups = new Set()

        this._featureGroup.addEventParent(this)
    },

    /**
     * The events we handle.
     *
     * The class reacts to zooming/dezooming to inflate as many markers as
     * possible with the new zoom without causing collisions.
     * @public
     * @inheritdoc
     */
    getEvents: function () {
        return {
            zoomend: this._zoomend,
        }
    },

    /**
     * Whether two markers collision when both are inflated
     *
     * @param {L.Point} distance - The distance between the center of both
     * markers
     * @param {L.InflatableMarker} marker1 - The first marker
     * @param {L.InflatableMarker} marker2 - The second marker
     * @return {boolean} Whether the markers are closer to each other than
     * the obstruction size
     */
    _mayObstruct: function (distance, marker1, marker2) {
        const marker1HalfSize = marker1.getInflatedSize().divideBy(2)
        const marker2HalfSize = marker2.getInflatedSize().divideBy(2)
        return (
            Math.abs(distance.x) <=
                marker1HalfSize.x + marker2HalfSize.x + this.options.obstructionSize.x &&
            Math.abs(distance.y) <=
                marker1HalfSize.y + marker2HalfSize.y + this.options.obstructionSize.y
        )
    },

    /**
     * Add a marker to the group and compute the collisions with already
     * existing markers
     * @param {L.Marker} layer - A marker to add (technically, it should be
     * any layer, but we kind of break the Liskov principle to make things
     * simpler for now...)
     * @public
     * @inheritdoc
     */
    addLayer: function (layer) {
        if (this.hasLayer(layer)) {
            return this
        }

        const marker = new InflatableMarker(layer._latlng, this, layer)
        let inhibited = false
        if (this._map) {
            const target = this._map.latLngToContainerPoint(layer._latlng)
            for (const [l, m] of this._markers) {
                const other = this._map.latLngToContainerPoint(l._latlng)
                if (this._mayObstruct(target.subtract(other), marker, m)) {
                    marker._addObstructiveMarker(m)
                    inhibited = true
                }
            }
        }

        this._markers.set(layer, marker)
        this._featureGroup.addLayer(marker)

        if (!inhibited) {
            marker._inflate()
            marker.redraw()
        }

        if (!this._inflatedMarkersAbove && !marker._inflated) {
            marker._bringToFront(DEFLATED_MARKERS_ZINDEX_OFFSET)
        }

        if (this._bounds == null) {
            this._bounds = L.latLngBounds(layer._latlng, layer._latlng)
        } else {
            this._bounds.extend(layer._latlng)
        }
    },

    /**
     * Remove a marker from the group and recompute the collisions of
     * previously collisioning markers
     * @param {L.Layer} layer - The layer to remove
     * @public
     * @inheritdoc
     */
    removeLayer: function (layer) {
        if (this._markers.has(layer)) {
            const marker = this._markers.get(layer)
            marker._clearObstructiveMarkers()
            this._featureGroup.removeLayer(marker)
            this._markers.delete(layer)
        }
    },

    /**
     * Remove all layers from this group and reset it completely
     * @public
     * @inheritdoc
     */
    clearLayers: function () {
        this._markers.clear()
        this._featureGroup.clearLayers()
        this._alreadyDisplayed = false // reset the layer as if it had never
        // been displayed
        this._bounds = null
    },

    /**
     * Returns the bounds of this group on the map
     * @return L.LatLngBounds
     * @public
     * @inheritdoc
     */
    getBounds: function () {
        return this._bounds
    },

    /**
     * Whether a marker has been added to the group
     * @param {L.Marker} layer - The marker looked for
     * @return {boolean} whether the layer belongs to this group
     * @public
     * @inheritdoc
     */
    hasLayer: function (layer) {
        return this._markers.has(layer)
    },

    /**
     * Recompute all collision sets for all markers
     * @private
     */
    _recomputeObstructions: async function () {
        for (const [l, m] of this._markers) {
            m._clearObstructiveMarkers()
        }

        const waitFor = delay => new Promise(resolve => setTimeout(resolve, delay))

        const iterator = this._markers.entries()
        let result = iterator.next()

        const allMarkers = [...this._iterateOnOwnAndOtherGroupsMarkers()]
        allMarkers.forEach(m => m[1]._computeBorders(this._map, this.options.obstructionSize))
        allMarkers.sort((m1, m2) => {
            return m1[1]._borders[0] - m2[1]._borders[0]
        })

        const process = L.bind(async function () {
            const start = new Date()

            while (!result.done) {
                const currentDate = new Date()
                if (currentDate - start > 200) {
                    break
                }
                const marker = result.value[1]

                const posNorth = this._bisectNorth(allMarkers, marker._borders[0])
                const posSouth = this._bisectSouth(allMarkers, marker._borders[2])

                const sortedByWest = allMarkers.slice(posNorth, posSouth).sort((m1, m2) => {
                    return m1[1]._borders[3] - m2[1]._borders[3]
                })
                const posWest = this._bisectWest(sortedByWest, marker._borders[3])
                const posEast = this._bisectEast(sortedByWest, marker._borders[1])

                sortedByWest.slice(posWest, posEast).forEach(m => {
                    if (marker !== m[1]) marker._addObstructiveMarker(m[1])
                })

                result = iterator.next()
            }

            if (!result.done) {
                process()
                return waitFor(50).then(process)
            } else {
                return true
            }
        }, this)

        return process()
    },

    _iterateOnOwnAndOtherGroupsMarkers: function* () {
        let iteratorOnGroups = this._otherGroups.values()
        let iteratorOnMarkers = this._markers.entries()
        let result = iteratorOnMarkers.next()
        while (!result.done) {
            yield result.value
            result = iteratorOnMarkers.next()
        }

        let gr = iteratorOnGroups.next()
        while (!gr.done) {
            iteratorOnMarkers = gr.value._markers.entries()
            result = iteratorOnMarkers.next()
            while (!result.done) {
                yield result.value
                result = iteratorOnMarkers.next()
            }
            gr = iteratorOnGroups.next()
        }
    },

    /**
     * React to this group being added onto a map
     *
     * Computation of the collision sets is delayed until this method is
     * called.
     * @param {L.Map} map - The leaflet map
     * @public
     * @inheritdoc
     */
    onAdd: function (map) {
        this._map = map
        this._recomputeObstructions().then(() => {
            this._featureGroup.addTo(map)
            if (!this._alreadyDisplayed) {
                this._alreadyDisplayed = true
                this.inflateAsManyAsPossible(true)
            }
        })
    },

    /**
     * React to this group being removed from a map
     *
     * The collision sets are not cleared at this point in case someone
     * wants to have a look at them, but they will be recomputed if the
     * group is added again onto a map anyway.
     * @param {L.Map} map - The leaflet map
     * @public
     * @inheritdoc
     */
    onRemove: function (map) {
        this._featureGroup.removeFrom(map)
        this._map = null
    },

    /**
     * Redraw all icons that are marked for update (after zooming in for
     * instance)
     * @private
     * @inheritdoc
     */
    _refreshIcons: function () {
        for (const [baseMarker, marker] of this._iterateOnOwnAndOtherGroupsMarkers()) {
            if (marker._iconNeedsUpdate) marker.redraw()
            marker._iconNeedsUpdate = false
        }
    },

    /**
     * Inflate as many deflated markers as possible without causing
     * collisions
     *
     * We don't actually go clever and guarantee that we display the
     * theoretical maximum number of markers. We just go through them in
     * order and avoid inflating a marker if it would collision with already
     * inflated markers.
     *
     * @param {boolean} reset - Start by deflating all markers before
     * inflating as many as possible
     * @public
     */
    inflateAsManyAsPossible: function (reset = false) {
        const inhibited = new Set()
        if (!reset) {
            // add all the markers that could obstruct the already inflated
            // markers
            for (const [layer, marker] of this._markers) {
                if (marker.inflated) {
                    for (const other of marker._obstructiveMarkers) {
                        inhibited.add(other)
                    }
                }
            }
        }

        for (const [layer, marker] of this._markers) {
            if (!inhibited.has(marker)) {
                marker._inflate()
                for (const other of marker._obstructiveMarkers) {
                    inhibited.add(other)
                    other._deflate()
                }
            }
        }
        this._refreshIcons()
    },

    /**
     * Deflate all markers
     * @public
     */
    deflateAll: function () {
        for (const [layer, marker] of this._markers) {
            marker._deflate()
        }
    },

    /**
     * React to zoom/dezoom by recomputing the collision between markers and
     * inflate as many as possible
     * @private
     */
    _zoomend: function () {
        this._recomputeObstructions().then(() => this.inflateAsManyAsPossible())
    },

    /**
     * Toggles between showing the inflating markers on top of all markers
     * (the normal state) and showing the deflating markers (so that we can
     * locate deflated markers previously hidden).
     * @public
     */
    toggleInflatedMarkersAbove() {
        if (this._inflatedMarkersAbove) {
            for (const [layer, marker] of this._markers) {
                if (!marker._inflated) {
                    marker._bringToFront(DEFLATED_MARKERS_ZINDEX_OFFSET)
                }
            }
            this._inflatedMarkersAbove = false
        } else {
            for (const [layer, marker] of this._markers) {
                if (!marker._inflated) {
                    marker._bringBackFromFront()
                }
            }
            this._inflatedMarkersAbove = true
        }
    },

    makeAwareOfOtherGroup(other) {
        this._otherGroups.add(other)
        other._otherGroups.add(this)
        if (this._map) {
            this._recomputeObstructions().then(() => this.inflateAsManyAsPossible())
        }
    },

    removeOtherGroup(other) {
        this._otherGroups.delete(other)
        other._otherGroups.delete(this)
        if (this._map) {
            this._recomputeObstructions().then(() => this.inflateAsManyAsPossible())
        }
    },

    /**
     * Bisect a map of markers to find the last one before the west boundary in parameter
     * The array has to be sorted.
     * @param {[L.Marker, L.InflatableMarker][]} markers An array of pairs [Marker, InflatableMarker]
     * @param {number} x The minimum X boundary
     * @private
     */
    _bisectWest(markers, x) {
        if (!markers.length) return markers.length
        let left = 0
        let right = markers.length - 1
        let pos = Math.trunc((left + right) / 2)
        while (pos > left) {
            if (x > markers[pos][1]._borders[1]) {
                left = pos
            } else {
                right = pos
            }
            pos = Math.trunc((left + right) / 2)
        }
        return markers.length > left && x > markers[left][1]._borders[1] ? left + 1 : left
    },

    /**
     * Bisect a map of markers to find the first one past the east boundary in parameter
     * The array has to be sorted.
     * @param {[L.Marker, L.InflatableMarker][]} markers An array of pairs [Marker, InflatableMarker]
     * @param {number} x The minimum X boundary
     * @private
     */
    _bisectEast(markers, x) {
        if (!markers.length) return -1
        let left = 0
        let right = markers.length - 1
        let pos = Math.ceil((left + right) / 2)
        while (pos < right) {
            if (x > markers[pos][1]._borders[3]) {
                left = pos
            } else {
                right = pos
            }
            pos = Math.ceil((left + right) / 2)
        }
        return markers.length > right && x < markers[right][1]._borders[3] ? right : right - 1
    },

    /**
     * Bisect a map of markers to find the first one past the east boundary in parameter
     * The array has to be sorted.
     * @param {[L.Marker, L.InflatableMarker][]} markers An array of pairs [Marker, InflatableMarker]
     * @param {number} y The minimum Y boundary
     * @private
     */
    _bisectNorth(markers, y) {
        if (!markers.length) return markers.length
        let left = 0
        let right = markers.length - 1
        let pos = Math.trunc((left + right) / 2)
        while (pos > left) {
            if (y > markers[pos][1]._borders[2]) {
                left = pos
            } else {
                right = pos
            }
            pos = Math.trunc((left + right) / 2)
        }
        return y > markers[left][1]._borders[2] ? left : left + 1
    },

    /**
     * Bisect a map of markers to find the first one past the east boundary in parameter
     * The array has to be sorted.
     * @param {[L.Marker, L.InflatableMarker][]} markers An array of pairs [Marker, InflatableMarker]
     * @param {number} y The minimum Y boundary
     * @private
     */
    _bisectSouth(markers, y) {
        if (!markers.length) return -1
        let left = 0
        let right = markers.length - 1
        let pos = Math.ceil((left + right) / 2)
        while (pos < right) {
            if (y > markers[pos][1]._borders[0]) {
                left = pos
            } else {
                right = pos
            }
            pos = Math.ceil((left + right) / 2)
        }
        return markers.length > right && y < markers[right][1]._borders[0] ? right : right - 1
    },
})

/**
 * Constructs an inflatable markers group
 * @constructs {L.InflatableMarkersGroup}
 * @param {L.InflatableMarkersGroup.options} options - the configuration
 * @return {L.InflatableMarkersGroup} The newly constructed group
 */
const inflatableMarkersGroup = function (options) {
    return new InflatableMarkersGroup(options)
}
const inflatableMarker = function (options) {
    return new InflatableMarker(options)
}

export default InflatableMarkersGroup
export { InflatableMarker, InflatableMarkersGroup, inflatableMarker, inflatableMarkersGroup }
